package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         42,
		Discription: "接雨水",
		Level:       3,
		Labels: map[string]int{
			"贪心": 1,
			"双指针滑动":  1,
		},
	})
}

// Trap2 和有一题移动短板很像
//  @param height
//  @return int
func Trap2(height []int) int {
	leftMax := height[0]
	rightMax := height[len(height)-1]
	i := 1
	j := len(height) - 2
	res := 0
	//优先移动短板的一边，每个点的面积为min(leftMax,rightMax)-height[i]，注意有可能小于0，小于0不需要加，但需更新最大值
	for i <= j {
		if leftMax < rightMax {
			//左边是短板，移动i
			if height[i] < leftMax {
				res += leftMax - height[i]
			} else {
				leftMax = height[i]
			}
			i++
		} else {
			//右边是短板，移动j
			if height[j] < rightMax {
				res += rightMax - height[j]
			} else {
				rightMax = height[j]
			}
			j--
		}
	}

	return res
}

func Trap(height []int) int {
	if len(height) < 3 {
		return 0
	}

	//从左到右遍历一遍，找出每个位置左边的最高点
	leftMax := make([]int, len(height))
	leftMax[1] = height[0]
	for i := 2; i <= len(height)-2; i++ {
		if height[i-1] > leftMax[i-1] {
			leftMax[i] = height[i-1]
		} else {
			leftMax[i] = leftMax[i-1]
		}
	}

	//从右到左遍历一遍，找出每个位置左边的最高点
	rightMax := make([]int, len(height))
	rightMax[len(height)-2] = height[len(height)-1]
	for i := len(height) - 3; i >= 1; i-- {
		if height[i+1] > rightMax[i+1] {
			rightMax[i] = height[i+1]
		} else {
			rightMax[i] = rightMax[i+1]
		}
	}

	//从[1,len-1]遍历一遍，每个位置的面积：min(leftMax[i],rightMax[i])-height[i]
	res := 0
	for i := 1; i <= len(height)-2; i++ {
		area := min(leftMax[i], rightMax[i]) - height[i]
		//注意可能小于0，小于0就是0，不需要加
		if area > 0 {
			res += area
		}
	}

	return res
}
